/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-airplanes-in-the-sky
   @Language: C++
   @Datetime: 16-02-09 08:19
   */

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
// Method 1, Two Arraies, Time 1151ms
class Solution {
public:
	/**
	 * @param intervals: An interval array
	 * @return: Count of airplanes are in the sky.
	 * Tip: See Method 2
	 */
	int countOfAirplanes(vector<Interval> &A) {
		// write your code here
		int ans=0, sum=0, i=0, j=0;
		vector<int> S(A.size()),E(A.size());
		for(i=A.size(); i--;){
			S[i] = A[i].start;
			E[i] = A[i].end;
		}
		sort(S.begin(),S.end());
		sort(E.begin(),E.end());
		for(i=j=0; i<S.size();){
			if (S[i]<E[j]){
				++sum;
				ans=max(ans,sum);
				++i;
			}
			else{
				--sum;
				++j;
			}
		}
		return ans;
	}
};

// Method 2, HashMap & Sort,Time 1017ms
class Solution {
	static bool pairless(const pair<int,int> &a,const pair<int,int> &b){
		return (a.first!=b.first ? a.first<b.first : a.second<b.second);
	}

public:
	/**
	 * @param intervals: An interval array
	 * @return: Count of airplanes are in the sky.
	 * Tip: when landing(end) time == flying(start) time, consider landing first.
	 * Let both start and end time points have weight 0, and 
	 * Statistics all time points weight using rules:
	 *     increasing by 1 if current point is start,
	 *     decreasing by 1 if current point is end.
	 * Calculate SUM of all time points' weight and Get Maximum
	 */
	int countOfAirplanes(vector<Interval> &A) {
		// write your code here
		unordered_map<int,int> hs;	// <time point, weight>
		int ans=0, sum=0, i=0;
		for(i=A.size(); i--;){
			++hs[A[i].start];
			--hs[A[i].end];
		}
		vector<pair<int,int> > vs(hs.begin(),hs.end());
		sort(vs.begin(),vs.end(),pairless);
		for(i=0, sum=0; i<vs.size(); ++i){
			sum += vs[i].second;	// sum of all time points weight
			ans = max(ans,sum);
		}
		return ans;
	}
};


// Method 3, Sort Pair, Time 1218ms
class Solution {
	static bool icless(const pair<int,char> &a, const pair<int,char> &b){
		return (a.first!=b.first ? a.first<b.first : a.second>b.second);
	}

public:
	/**
	 * @param intervals: An interval array
	 * @return: Count of airplanes are in the sky.
	 * Tip: See Method 2
	 */
	int countOfAirplanes(vector<Interval> &A) {
		// write your code here
		vector<pair<int,char> > v;
		int ans=0, sum=0, i=0;
		for (i=A.size(); i--;){
			v.push_back(make_pair(A[i].start,0));
			v.push_back(make_pair(A[i].end,1));
		}
		sort(v.begin(), v.end(), icless);
		for (i=sum=0; i<v.size(); ++i){
			if (v[i].second==0){	// start time point
				++sum;				// sum of weight
				ans = max(ans,sum);
			}
			else --sum;
		}
		return ans;
	}
};

//Method 4, Binary Search Tree, Time 1177ms
class Solution {
	static bool intervaless(const Interval &a, const Interval &b) {
		return (a.start!=b.start ? a.start<b.start : a.end<b.end);
	}

public:
	/**
	 * @param intervals: An interval array
	 * @return: Count of airplanes are in the sky.
	 * Tip: If current end time > start time, now have size airplanes
	 */
	int countOfAirplanes(vector<Interval> &A) {
		int ans=0, i=0;
		multiset<int> bst;
		sort(A.begin(),A.end(),intervaless);
		for (i=0; i<A.size(); ++i) {
			bst.emplace(A[i].end);
			while (*bst.begin() <= A[i].start) {
				bst.erase(bst.begin());
			}
			ans = max(ans,(int)bst.size());
		}
		return ans;
	}
};

// Method 5, Heap Sort, Time 853ms
class Solution {
	static bool intervaless(const Interval &a, const Interval &b) {
		return (a.start!=b.start ? a.start<b.start : a.end<b.end);
	}

public:
	/**
	 * @param intervals: An interval array
	 * @return: Count of airplanes are in the sky.
	 * Tip: If current end time > start time, now have size airplanes
	 */
	int countOfAirplanes(vector<Interval> &A) {
		int ans=0, i=0;
		priority_queue<int,vector<int>,greater<int> > minheap;
		sort(A.begin(),A.end(),intervaless);
		for (i=0; i<A.size(); ++i) {
			minheap.push(A[i].end);
			for (; minheap.top()<=A[i].start; minheap.pop());
			ans = max(ans,(int)minheap.size());
		}
		return ans;
	}
};
